package leetcode.stack_queue;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Lc2462 {

    public long totalCost(int[] costs, int k, int candidates) {
        int ans = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]));
        int l = 0, r = costs.length - 1;
        while (l < candidates && l < costs.length) {
            pq.offer(new int[]{costs[l], l});
            l++;
        }
        while (l <= r && r >= costs.length - candidates) {
            pq.offer(new int[]{costs[r], r});
            r--;
        }
        while (k-- > 0 && !pq.isEmpty()) {
            ans += pq.peek()[0];
            int idx = pq.poll()[1];
            if (l <= r) { //还有未进队的工人
                if (idx < l) {
                    pq.offer(new int[]{costs[l], l});
                    l++;
                } else {
                    pq.offer(new int[]{costs[r], r});
                    r--;
                }
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Lc2462 lc2462 = new Lc2462();
        int[] c = {17,12,10,2,7,2,11,20,8};
        int k = 3;
        int ca = 4;
        System.out.println(lc2462.totalCost(c, k, ca));
    }
}
